package com.vinfai.datastructures.link;

import java.io.Serializable;
import java.util.Collections;
import java.util.EnumSet;
import java.util.Stack;

/**
 * 
 * 简单链表
 * 1.尾部增加形式,增删改查
 * 2.链表反转
 * @author vinfai
 *
 * @param <T> 节点数据类型
 */
public class SimpleLink<T> implements Serializable{
	//头结点
	private Node<T> header = null;
	//最后的节点
	private Node<T> tail = null;
	public SimpleLink(){
	}
	
	public void add(T data){
		Node<T> newNode = new Node(data);
		if(header==null){
			header = tail = newNode;
		}else{
			tail.next = newNode;//在tail后增加一个节点
			tail = newNode;//tail指向最后一个节点
		}
	}
	
	public void remove(Node<T> node){
		if(node==null||node.getData()==null){
			throw new RuntimeException("node data is null.");
		}
		//头结点特殊处理,
		Node curr = header,pre = null;
		boolean find = false;
		while(curr!=null&&!find){
			if(curr.getData().equals(node.getData())){
				if(pre==null) removeFirst(); //pre==null表示删除的为头节点
				else{
					pre.next = curr.next; //删除当前节点
					if(curr==tail){ //删除尾节点,tail处理
						tail = pre;
					}
				}
				find = true;
			}else{
				pre = curr;
				curr = curr.next;
			}
		}
	}
	
	public void removeFirst(){
		if(!isEmpty()){
			header = header.next;
		}
	}
	
	public boolean isEmpty(){
		return header==null;
	}
	
	public void listNodes(){
		StringBuilder buffer = new StringBuilder();
		Node curr = header;
		while(curr!=null){
			if(curr.next!=null)
				buffer.append(curr.getData()+" --> ");
			else
				buffer.append(curr.getData());
			curr = curr.next;
		}
		System.out.println(buffer.toString());
	}
	
	public void reverseList(){
		//单个节点
		if(header==null||header.next==null){
			System.out.println("header is null or header.next is null "+header.getData());
		}
		Node p1,p2,p3;
		p1 = header;
		p2 = p1.next;
		p3 = p2.next;
		p1.next = null; //p1要变成尾指针，所以指向NULL  
		while(p3!=null){
			p2.next = p1;
			p1 = p2; //向后移动一位
			p2 = p3;
			p3 = p3.next;
		}
		p2.next = p1; //p3指向了NULL，p2反向  
		header = p2; //头指针指向之前的尾指针  
		
		Node node = header;
		StringBuilder buffer = new StringBuilder();
		while(node!=null){
			buffer.append(node.getData()+" -->");
			node = node.next;
		}
		System.out.println(buffer.toString());
	}
	
	public void reverseListByStack(){
//		Stack<T>  stack = new Stack<T>();
//		Boolean.TRUE;
//		EnumSet<Enum<E>>
		
	}
	
	
	/**
	 * 增加在某个节点之后
	 * @param data
	 * @param node
	 * @return
	 */
	public Node<T> add(T data,Node<T> node){
		if(data==null){
			throw new RuntimeException("add data is null.");
		}
		Node<T> newNode = new Node(data);
		if(node==null){
			this.add(data);
		}else{
			Node<T> curr = this.findNode(node);
			if(curr!=null){
				newNode.next = curr.next;
				curr.next = newNode;
				if(curr==tail){
					tail = newNode;
				}
			}
		}
		return newNode;
	}
	
	public Node<T> findNode(Node<T> node){
		if(node==null||node.getData()==null){
			throw new RuntimeException("find node data is null");
		}
		Node<T> rs = null;
		Node<T> h = header;
		while(h!=null){
			if(h.getData().equals(node.getData())){
				rs = h;
				break;
			}else{
				h = h.next;
			}
		}
		return rs;
	}
	
	public static void main(String[] args){
		SimpleLink<Integer> link = new SimpleLink<Integer>();
		SimpleLink<Integer>.Node<Integer> node = link.new Node<Integer>(4);
		link.add(100);
		link.add(1);
		link.add(2);
		link.add(3);
		link.add(4);
		link.add(6);
		link.add(7);
		link.listNodes();
		link.add(5,node);
		link.listNodes();
		
		SimpleLink<Integer>.Node<Integer> node2 = link.new Node<Integer>(7);
		link.remove(node2);
		link.listNodes();
		System.out.println("tail:"+link.tail.getData());
		
		link.reverseList();
	}
	
	private class Node<T>{
		T data;
		Node<T> next;
		public Node(T data){
			this.data = data;
			this.next = null;
		}
		public T getData() {
			return data;
		}
		public void setData(T data) {
			this.data = data;
		}
		public Node<T> getNext() {
			return next;
		}
		public void setNext(Node<T> next) {
			this.next = next;
		}
	}
}
